|
|
CS 116 Tutorial 9 (Solutions): Search & Sorting Algorithms, Dictionaries, and Classes (Module 8 and 9)
Reminders:
- Assignment 8 due Friday, 2 week
Searching and Sorting Algorithms
-
Sometimes a list could be very close to its sorted version, such
tha it looks a like a rotation of a sorted list. For example,
[4, 6, 1, 3] is a rotation of a sorted list of [1, 3, 4, 6],
when every element is shifted by 2 to the right. We'll called
this type of sorted list, r-Sorted list.
Write a function, restore_sorted_list, that consume
a r-Sorted list and mutates it to a sorted lists.
Example:
L = [4, 6, 1, 3]
restore_sorted_list(L) => None
L => [1, 3, 4,6]
Solution
# Finding rotation spot using linear search algorithm:
def find_start(rSortedList):
'''
returns a natural that is the index of the first occurance of
the smallest number of rSortedList.
find_end: (listof int) -> (anyof Nat)
'''
if L:
for i in range(1, len(L)):
if L[i] < L[i-1]:
return i
return 0
# Main Function
def restore_sorted_list(rList):
'''
returns None but mutates rList such that it is back to its
sorted version.
Effects: mutates rList
restore_sorted_list: (listof Int) -> None
Exmaples:
L = [4, 6, 1, 3]
restore_sorted_list(L) => None
L => [1, 3, 4, 6]
L = []
restore_sorted_list(L) => None
L => []
'''
pivot = find_end(rList)
if pivot > 0: # The list isn't sorted.
# Create a correct version for camparison
cor_ver = [0] * len(rList)
for i in range(len(rList)):
cor_pos = i + pivot % len(rList) #in case we exceed len(L)
cor_ver[cor_pos] = rList[i]
for i in range(Len(rList)): # Mutates original list accordingly
rList[i] = cor_ver[i]
Alternate Solution:
# Helper Function #2: partial_reverse
def partial_reverse(L, st, end):
'''
returns None but mutates L by reversing the elements from
index st to index end.
Effects: Mutates L
partial_reverse: (listof Any) Nat Nat -> None
'''
i = st
j = end
while i < j:
temp = L[i]
L[i] = L[j]
L[j] = temp
# Main Function
def restore_sorted_list(rList):
'''
returns None but mutates rList such that it is back to its
sorted version.
Effects: mutates rList
restore_sorted_list: (listof Int) -> None
Exmaples:
L = [4, 6, 1, 3]
restore_sorted_list(L) => None
L => [1, 3, 4, 6]
L = []
restore_sorted_list(L) => None
L => []
'''
pivot = find_end(rList)
if pivot > 0:
partial_reverse(rList, 0, pivot-1)
partial_reverse(rList, pivot, len(rList) - 1)
partial_reverse(rList, 0, len(rList) - 1)
Tests:
L = []
check.expect("Empty list", restore_sorted_list(L), None)
check.expect("Empty list - mutaiton", L, [])
L = [-1, 0, 2, 4, 6, 9, 10]
check.expect("Sorted list", restore_sorted_list(L), None)
check.expect("Sorted list - mutation", L, [1, 2, 3, 4])
L = [2, 4, 6, 9, 10, -1, 0]
check.expect("Large Rotation", restore_sorted_list(L), None)
check.expect("Large Rotation - mutation", L, [-1, 0, 2, 4, 6, 9, 10])
L = [10, -1, 0, 2, 4, 6, 9]
check.expect("Small rotation", restore_sorted_list(L), None)
check.expect("Small rotation - mutation", L, [[-1, 0, 2, 4, 6, 9, 10])
Dictionaries
-
Write a function list_multiples that consumes a
string s and returns a list
in alphabetical order containing every character in
s that appears more than once.
Use dictionaries.
Examples:
list_multiples("abcd") => []
list_multiples("bacaba") => ["a", "b"]
list_multiples("gtddyucaadsa") => ["a", "d"]
Solutions
def list_multiples(s):
'''
returns a list containing every character in s which appears more
than once, in sorted order.
list_multiples: Str -> (listof Str)
Examples:
list_multiples("") => []
list_multiples("abc") => []
list_multiples("bacaba") => ['a', 'b']
'''
d = {}
for char in s:
if char in d:
d[char] += 1
else:
d[char] = 1
more_than_once = []
for key in d:
if d[key] > 1:
more_than_once.append(key)
return sorted(more_than_once)
# Tests:
check.expect("Q1t1",list_multiples(""),[])
check.expect("Q1t2",list_multiples("a"),[])
check.expect("Q1t3",list_multiples("ab"),[])
check.expect("Q1t4",list_multiples("abb"),["b"])
check.expect("Q1t5",list_multiples("bbaaarr"),["a","b","r"])
check.expect("Q1t6",list_multiples("gtddyucaadsa"),["a","d"])
-
Write a function xor that consumes two dictionaries
(d1 and d2), and returns
a new dictionary.
The returned dictionary will contain all the keys that
appear in exactly one of d1 or d2 (but
not both).
The value associated with each key will be the same as the one
found in the original dictionary.
Examples:
d1 = {1:'a', 2:'b', 3:'c', 4:'d'}
d2 = {5:'e', 6:'f', 7:'g', 8:'h'}
d3 = {5:'q', 6:'l', 7:'c', 8:'e'}
xor(d1, d2) => {1:'a', 2:'b', 3:'c', 4:'d', 5:'e', 6:'f', 7:'g', 8:'h'}
xor(d2, d3) => {}
Classes
Student is a class with the fields: name, faculty, program,
year, and courses:
name is a non-empty string representing the
student's full name;faculty is a non-empty string representing the
student's faculty;
Full version: e.g "Environment" rather than "Env"
program is a non-empty string representing the
person's program (or major);
e.g. "Honours Mathematics" and "Art and Business"
year is a natural number representing the
student's academic year;courses is a list of strings representing the
courses the student is taking in the current term;
Below is the definition of the __init__,
__repr__, __eq__ function for the
Student class.
class Student:
""" Fields: name (Str),
faculty (str),
program (str)
year (Nat),
courses for the term (Listof Str)"""
# Constructor for Student:
# Calling Student(full_name, fac, prog, yr, titles) creates an
# object with name, faculty, program, year, courses initialized to
# full_name, fac, prog, yr, titles, respectively
# Requires:
# * full_name is a non-empty string for the student's name
# * fac is a non-empty string for the full faculty name (e.g. Mathematics not Math)
# * prog is non-empty string for program of study (e.g. "Psychology" or "Applied Mathematics")
# * yr is a positive integer, for student's year of study
# * titles is a list containing the abbreviated version of courses student
# is currently taking(e.g. "CS 116" rather than "Intro to Comp Sci 2")
# Note: __init__ is not called directly by name
def __init__(self, full_name, fac, prog, yr, titles):
self.name = full_name
self.faculty = fac
self.program = prog
self.year = yr
self.courses = titles
# Calling student1 == student2 is equivalent to calling self.__eq__(other)
# to compare fields of self and other.
# Note: __eq__ is not called directly by name
def __eq__(self, other):
if isinstance(other, Student):
return self.name == other.name and \
self.faculty == other.faculty and \
self.year == other.year and \
self.program == other.program and \
self.courses == other.courses
else:
return False
# Calling print(s), for Student s, will print the string returned by __repr__.
# Displaying the value in the interactions window will use the returned string
# as well
# Note: __repr__ is not called directly
def __repr__(self):
s = "{} ({}, {}, {}, {})".format(self.name, self.faculty, self.program, self.year, self.courses)
# returns Name (Faculty, Program, Year, Courses)
return s
def add_courses(self, loc):
'''
mutates self.courses by adding the courses in loc that are not already
in self.courses and prints the number of courses they are enrolled in.
Effects:
* Mutates self
* prints to the screen
add_courses: Student (listof Str) -> None
'''
for course in loc:
if course not in self.courses:
self.courses.append(course)
print('{0} is currently taking {1} course(s).'.format(self.name, len(self.courses)))
Examples of Student Objects:
YQ_W = Student("Y.Q. Wang", "Mathematics", "Math/Teaching", 2,
["MATH 239, STAT 231, CO 250, ENGL 109D"])
Nicole_V = Student("Nicole Velocci", "Mathematics", "Statistics",
2, ["ENGL 109", "MATH 237"])
Paul_S = Student("Paul Shen", "Applied Health Science", "Health Studies", 2,
["MATH 106", "CS 234", "CS 200", "HLTH 273", "ECON 101"])
Steve_Z = Student("Steve Zhang", "Arts", "Psychology", 2,
["PSYCH 207", "PSYCH 261", "PSYCH 202"])
Jason_A = Student("Jason Arl", "Mathematics", "Honours Mathematics", 2,
["MATH 235", "MATH 237", "STAT 231"])
Tyler_H = Student("Tyler Hall", "Mathematics", "Mathematical Physics", 1,
["MATH 136", "MATH 148", "STAT 230", "ENGL 119", "CHEM 121"])
Kyle_H = Student("Kyle Hauck", "Mathematics", "Applied Mathematics", 3,
["AMATH 351", "AMATH 363", "AMATH 342", "STAT 332"])
Logan_S = Student("Logan Stanley", "Science","Chemistry", 1,
["CHEM 120", "MATH 127", "PHYS 111"])
Liza_W = Student("Liza Wang", "Engineering", "Software Engineering", 3,
["BUS 121", "CS 343","CS 450"])
Dan_W = Student("Dan Wolczuk", "Mathematics", "Pure Mathematics", 1,
["MATH 148", "MATH 146", "CS 116"])
Write a class method add_courses in the student class, which consumes a list of strings, loc, and prints the number of courses the student current is taking and adds course to the student's courses.
Examples:
Paul_S.add_courses(["HLTH 230"]) will print "Paul Shen is currently taking 6 course(s)."
and Paul_S.courses == ["MATH 106", "CS 234", "CS 200", "HLTH 273", "ECON 101", "HLTH 230"]
Nicole_V.add_courses([]) will print "Nicole Velocci is currently taking 2 course(s)."
and Nicole_V.courses == ["ENGL 109", "MATH 237"]
Solution
import check
"""Solution to Q3 should be written within the class, please go up to the class method to check"""
## Tests for Question 3
## Paul_S.add_courses(["HLTH 230"]) will:
## - print "Paul Shen is currently taking 6 course(s)."
## - update Paul_S.courses to ["MATH 106", "CS 234", "CS 200", "HLTH 273", "ECON 101", "HLTH 230"]
## Nicole_V.add_courses([]) will:
## - print "Nicole Velocci is currently taking 2 course(s)."
## - update Nicole_V.courses to ["ENGL 109", "MATH 237"]
check.set_screen("Paul Shen is currently taking 6 course(s).")
check.expect("add-courses-1", Paul_S.add_courses(["HLTH 230"]), None)
check.expect("add-courses-1 - courses list", Paul_S.courses,
["MATH 106", "CS 234", "CS 200", "HLTH 273", "ECON 101", "HLTH 230"])
check.set_screen("Nicole Velocci is currently taking 2 course(s).")
check.expect("add-courses-2", Nicole_V.add_courses([]), None)
check.expect("add-courses-2 - courses list", Nicole_V.courses, ["ENGL 109", "MATH 237"])
Write a function organize_by_year which consumes a list of student objects, loS, and returns a dictionary where the names of the students will be in a list, in the same order they appear in loS and categorized by the year.
Examples:
organize_by_year([]) => {}
L = [Paul_S, Nicole_V, Dan_W]
organize_by_year(L) => {1: ["Dan Wolczuk"], 2:['Paul Shen', 'Nicole Velocci']}
Solution
import check
## organize_by_year(loS) returns a dictionary where the names of student objects
## in the list, loS, are categorized by the academic year.
## organize_by_year: (Listof students) => (dictof Nat (Listof Str))
## Example:
## L = [Paul_S, Nicole_V, Dan_W]
## organize_by_year => {1: ["Dan Wolczuk"], 2:['Paul Shen', 'Nicole Velocci']}
## organize_by_year([]) => {}
group = [Jason_A, Dan_W, Liza_W, Kyle_H, Logan_S, Tyler_H, Paul_S]
def organize_by_year(loS):
result = {}
for s in loS:
name = s.name
year = s.year
if year not in result:
result[year] = [name]
else:
result[year].append(name)
return result
# Tests
check.expect("organize-empty", organize_by_year([]), {})
check.expect("organize-one-student", organize_by_year([Paul_S]), {2:['Paul Shen']})
L = [Paul_S, Nicole_V, Dan_W]
check.expect("organize-typical", organize_by_year(L),
{1: ["Dan Wolczuk"], 2:['Paul Shen', 'Nicole Velocci']})
Write a function is_same_faculty that consumes a non-empty list of students, los, and returns True if all the students belongs in the same faculty. Otherwise, the method returns False
Example:
is_same_faculty([Nicole_V]) => True
Mathies = [Nicole_V, Dan_W]
is_same_faculty(Mathies) => True
mixed = [Paul_S, Logan_S]
is_same_faculty(mixed) => False
Solution
import check
## Question 5
## is_same_faculty(loS) consumes a non-empty list of students, loS.
## It returns True if all the students in loS belongs in the same faculty;
## otherwise, False.
## is_same_faculty: (Listof Student) -> Bool
## requirements: len(loS) > 0
# Examples:
# is_same_faculty([Nicole_V]) => True
# Mathies = [Nicole_V, Dan_W]
# is_same_faculty(Mathies) => True
# mixed = [Paul_S, Logan_S]
# is_same_faculty(mixed) => False
def is_same_faculty(loS):
faculty = loS[0].faculty
for s in loS:
if s.faculty != faculty:
return False
return True
# Tests
check.expect("is_same: one student", is_same_faculty([Nicole_V]), True)
check.expect("is_same: all same", is_same_faculty([Nicole_V, Dan_W]), True)
check.expect("is_same: different", is_same_faculty([Paul_S, Logan_S]), False)
|